#include<vector>
#include<iostream>
using namespace std;

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        int a, b, c, l, r, mid;
        int res = 0;
        for (int i = 0; i < n; i ++) {
            a = nums[i];
            for (int j = n - 1; j >= i + 1; j--) {
                c = nums[j];
                // 则b只能在(c - a, a + c)之间, 而 b < c
                // 所以b只能在 (c - a, c)之间

                l = i + 1, r = j - 1;
                while (l < r) {
                    mid = (l + r) / 2;
                    b = nums[mid];

                    if (b <= c - a) {
                        l++;
                    } else {
                        r--;
                    }
                }
                cout << (j - l) << endl;
                res += (j - l);
            }
        }

        return res;
    }
};




// 这段代码的核心意图是计算数组 `nums` 中可以组成三角形的三元组数量，但目前存在**逻辑与实现层面的多处错误**，无法得到正确结果。

// 下面先分析问题，再给出正确版本。

// ---

// ### ❌ 存在的问题

// 1. **没有排序**
//    三角形判定需要有序数组，否则不满足 `a ≤ b ≤ c` 的前提就无法做出正确判断。

// 2. **双重循环方向不合理**
//    外层 `i` 从前往后、内层 `j` 从后往前，会破坏三角形三边关系，尤其是 `b` 的搜索区间 `(c - a, c)` 逻辑不清晰。

// 3. **二分查找逻辑错误**
//    `while (l < r)` 内部的移动条件不正确。`b <= c - a` 时，说明 `b` 太小，`l` 应右移；否则左移，但代码中使用的是 `r--`，不是标准二分。

// 4. **统计方式错误**
//    `res += (j - l)` 只在某些情况下成立，当前实现没有保证每次统计的范围是合法的。

// ---

// ### ✅ 正确写法与解释

// 可以用排序 + 双指针法，时间复杂度为 `O(n^2)`。
// 思路如下：

// 1. 排序数组，确保 `a ≤ b ≤ c`。
// 2. 固定最大边 `c = nums[k]`，在 `[0, k-1]` 范围内用双指针判断有多少 `(a, b)` 能满足 `a + b > c`。
// 3. 若满足则累加 `(r - l)`，否则移动左指针。

// ```cpp
// #include <vector>
// #include <algorithm>
// using namespace std;

// class Solution {
// public:
//     int triangleNumber(vector<int>& nums) {
//         sort(nums.begin(), nums.end());
//         int n = nums.size();
//         int res = 0;

//         for (int k = n - 1; k >= 2; k--) { // 固定最大边
//             int c = nums[k];
//             int l = 0, r = k - 1;

//             while (l < r) {
//                 if (nums[l] + nums[r] > c) {
//                     res += (r - l); // [l, r-1] 都能与 r 组成三角形
//                     r--;
//                 } else {
//                     l++;
//                 }
//             }
//         }
//         return res;
//     }
// };
// ```

// ---

// ### 💡算法解释（通俗版）

// 假设数组排序后为 `[a1, a2, ..., an]`。
// 选定最大的边 `c = an`。
// 如果某一对 `(a_i, a_j)` 满足 `a_i + a_j > c`，那么所有比 `a_i` 大的数（到 `a_{j-1}`）都能与 `a_j` 组成三角形。
// 这样一次判断可以同时确定多个有效三元组，大大减少复杂度。

// ---

// ### ✅ 示例

// 输入

// ```cpp
// nums = {2, 2, 3, 4};
// ```

// 排序后为 `[2, 2, 3, 4]`
// 合法三角形有：

// * (2, 3, 4)
// * (2, 3, 4)
// * (2, 2, 3)

// 输出结果为 `3`，程序可正确返回。
